Research
I work in the intersection of theoretical computer science and discrete mathematics. In particular, currently I am interested in approximation algorithms, discrepancy theory and related questions in high dimensional convex geometry.
Lecture notes and expositions
- Analysis of Boolean Functions (lecture notes for a graduate special topics course being held in Fall 2025)
- Lattices (lecture notes for a graduate special topics course held in Winter 2023)
- Networks and Combinatorial Optimization (lecture notes for a graduate course held annually)
- Asymptotic Convex Geometry (lecture notes for a graduate special topics course held in Winter 2021)
- Probabilistic Combinatorics (lecture notes for a graduate special topics course held in Winter 2019)
- Integer Optimization and Lattices (lecture notes for a graduate special topics course held in Spring 2016)
- The Lasserre Hierarchy in Approximation Algorithms (notes for a tutorial held at MAPSP 2013; slides)
- Discrete optimization (lecture notes for an undergraduate course held annually)
Students
Current PhD advisees:
- Patrick O'Melveny
- Mathews Boban
Graduated Ph.D.:
- Rainie Heck (2025)
- Sally Dong (2024; co-advised with Yin Tat Lee)
- Victor Reis (2023)
- Yihao Zhang (2022)
- Sami Davies (2021)
- Harishandra Ramadas (2017)
- Rebecca Hoberg (2017)
Graduated Master students:
- Elaine Levey
Awards
- Trevisan Prize 2025
- FOCS 2023 Best Paper Prize
- Gödel Prize 2023
- IPCO 2023 Best Paper Prize
- Delbert Ray Fulkerson Prize (2018)
- STOC 2014 Best Paper Prize
- SODA 2014 Best Paper Prize
- STOC 2010 Best Paper Prize
- Best Computer Science Graduate at TU Dortmund (2007)
Selected Funding
- NSF SMALL (2023-2026)
- NSF CAREER grant (2017-2022)
- Packard Foundation Fellowship (2016-2021)
- Sloan Research Fellowship (2015-2017)
- Feodor Lynen post-doctoral fellowship (2011-2012)
Teaching at the University of Washington
- Winter 2026 - Math 409 - Discrete Optimization (undergraduate course)
- Fall 2025 - Math 581A - Analysis of Boolean Functions (graduate special topics course)
- Winter 2025 - Math 409 - Discrete Optimization (undergraduate course)
- Fall 2024 - CSE 521 - Design and Analysis of Algorithms
- Winter 2024 - CSE 531 - Computational Complexity
- Fall 2023 - Math 514 - Networks and Combinatorial Optimization
- Winter 2023 - CSE599S - Lattices (graduate special topics course)
- Fall 2022 - Math 514 - Networks and Combinatorial Optimization (graduate course)
- Spring 2022 - Math 409 - Discrete Optimization (undergraduate course)
- Spring 2021 - CSE 311 - Foundations of Computing 1 (undergraduate course)
- Winter 2021 - Math 582F - Asymptotic Convex Geometry (graduate special topics course)
- Fall 2020 - Math 514 - Network Optimization (graduate course)
- Spring 2020 - Math 409 - Discrete Optimization (undergraduate course)
- Spring 2019 - CSE 311 - Foundations of Computing 1 (undergraduate course)
- Winter 2019 - Math 582D - Probabilistic Combinatorics (graduate special topics course)
- Winter 2018 - Math 514 - Network Optimization (graduate course)
- Spring 2017 - Math 409 - Discrete Optimization (undergraduate course)
- Winter 2017 - CSE 421 - Introduction to Algorithms (undergraduate course)
- Fall 2016 - Math 514 - Network Optimization (graduate course)
- Spring 2016 - Math 583D - Integer Optimization and Lattices (graduate special topics course)
- Winter 2016 - CSE 421 - Introduction to Algorithms (undergraduate course)
- Spring 2015 - Math 409 - Discrete Optimization (undergraduate course)
- Winter 2015 - Math 126 - Calculus with Analytic Geometry III (undergraduate course)
- Fall 2014 - Math 514 - Network Optimization (graduate course)
- Spring 2014 - Math 126 - Calculus with Analytic Geometry III (undergraduate course)
- Winter 2014 - Math 409 - Discrete Optimization (undergraduate course)
Professional service
- Editor for the Journal of the ACM (2024+)
- Editor for Theory of Computing (TOC) (2019-2023)
- Co-organizer for a semester-long program in fall 2017 at the Simons Institute for the Theory of Computing at UC Berkeley
- Organizer of an Oberwolfach Workshop on "Combinatorial Optimization" in November 2024
- Conference program committee:
- IPCO 2026
- STOC 2025
- APPROX 2024
- FOCS 2023
- STOC 2022
- SODA 2022
- ESA 2020
- FOCS 2018
- FOCS 2015
- SODA 2015
- ESA 2015
- WAOA 2015
- APPROX 2014
- WAOA 2014
Publications (chronologically):
- The Subspace Flatness Conjecture. Proceedings article for the 2026 ICM in Pittsburgh, USA.
- A parameterized linear formulation of the integer hull. F. Eisenbrand, T. Rothvoss. SODA 2026 (to appear). Slides.
- Excluding a Line Minor via Design Matrices and Column Bounds for the Circuit Imbalance Measure. N. Singer, D. Dadush, F. Eisenbrand, R. Pinchasi, T. Rothvoss. SODA 2026 (to appear).
- Tensor Concentration Inequalities: A Geometric Approach. A. Bandeira, S. Gopi, H. Jiang, K. Lucca, T. Rothvoss. STOC 2025. See also the math journal version A Geometric Perspective on the Injective Norm of Sums of Random Tensors
- Forall-exist statements in pseudo-polynomial time. E. Bach, F. Eisenbrand, T. Rothvoss, Robert Weismantel. SODA 2025.
- Optimal Online Discrepancy Minimization. J. Kulkarni, V. Reis, T. Rothvoss. STOC 2024 (see Arxiv 2308.01406). Slides.
- Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity. S. Dong, T. Rothvoss. IPCO 2024.
- The Subspace Flatness Conjecture and Faster Integer Programming. V. Reis, T. Rothvoss. FOCS 2023 (best paper award). Arxiv 2303.14605 (2023). Slides. Video. A longer version with three 1-hour talks given at Georgia Tech which also covers the Micciancio-Voulgaris algorithm and the Reverse Minkowski Theorem: Slides. Video part 1. Video part 2. Video part 3. The paper was covered in Quanta and in Communications of the ACM.
- The Vector Balancing Constant for Zonotopes. L. Heck, V. Reis, T. Rothvoss. Arxiv 2210.16460 (2022)
- From approximate to exact integer programming. D. Dadush, F. Eisenbrand, T. Rothvoss. IPCO 2023 (also Arxiv 2211.03859 and Math Programming B journal version)
- Approximate Caratheodory bounds via Discrepancy Theory. V. Reis, T. Rothvoss. Arxiv 2207.03614 (2022).
- Approximate CVP in time 2^0.802n -- now in any norm!. T. Rothvoss, M. Venzin. IPCO 2022.
- Tight bounds on the Fourier growth of bounded functions on the hypercube. S. Iyer, A. Rao, V. Reis, T. Rothvoss, A. Yehudayoff. To be submitted (2021).
- On the Hardness of Scheduling With Non-Uniform Communication Delays. S. Davies, J. Kulkarni, T. Rothvoss, S. Sandeep, J. Tarnawski, Y. Zhang. SODA 2022.
- Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. S. Davies, J. Kulkarni, T. Rothvoss, J. Tarnawski, Y. Zhang. SODA 2021.
- Scheduling with Communication Delays via LP Hierarchies and Clustering. S. Davies, J. Kulkarni, T. Rothvoss, J. Tarnawski, Y. Zhang. FOCS 2020.
- Vector Balancing in Lebesgue Spaces. V. Reis, T. Rothvoss. Random Structures & Algorithms (to appear; 2022).
- A Tale of Santa Claus, Hypergraphs and Matroids. S. Davies, T. Rothvoss, Y. Zhang. SODA 2020. (see Arxiv 1807.07189, video of the older version with a 6-apx)
- Linear Size Sparsifier and the Geometry of the Operator Norm Ball. V. Reis and T. Rothvoss. SODA 2020 (see Arxiv 1907.02145)
- A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. R. Hoberg, T. Rothvoss. SODA 2019. (see Arxiv ID 1806.04484).
- An improved deterministic rescaling for linear programming algorithms. R. Hoberg and T. Rothvoss. IPCO 2017 (Arxiv).
- Deterministic discrepancy minimization via the multiplicative weight update method. A. Levy, H. Ramadas, T. Rothvoss. IPCO 2017 (Arxiv)
- Number Balancing is as hard as Minkowski's Theorem and Shortest Vector. R. Hoberg, H. Ramadas, T. Rothvoss, X. Yang. IPCO 2017 (Arxiv)
- A Logarithmic Additive Integrality Gap for Bin Packing. R. Hoberg and T. Rothvoss. SODA 2017 (Arxiv ID 1503.08796 from 2015). Slides.
- A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. E. Levey and T. Rothvoss. STOC'16 (Arxiv, slides).
- Constructive discrepancy minimization for convex sets. T. Rothvoss. FOCS 2014. Invited to the SICOMP Special Issue for FOCS'14. See also ArXiv ID 1404.0339. Slides. Video.
- The matching polytope has exponential extension complexity. T. Rothvoß. STOC 2014. Winner of the STOC 2014 Best Paper Prize. See also ArXiv ID 1311.2369. Slides. Video.
- Polynomiality for Bin Packing with a Constant Number of Item Types. M.X. Goemans and T. Rothvoß. SODA 2014 (Co-winner of Best Paper Award; invited to the Journal of the ACM, see also ArXiv ID 1307.5108. 2013). Slides. Video (talk given by my co-author).
- A direct proof for Lovett's bound on the communication complexity of low rank matrices. T. Rothvoss. Arxiv ID 1409.6366. Slides.
- Approximating Bin Packing within O(log OPT log log OPT) bins. T. Rothvoß. FOCS 2013. Invited to the SICOMP Special Issue for FOCS'13 (see also ArXiv ID 1301.4010. 2013). Slides. Video.
- Steiner Tree Approximation via Iterative Randomized Rounding. J. Byrka, F. Grandoni, T. Rothvoss and L. Sanità. Invited submission to the Journal of the ACM. Journal version of the STOC'10 paper. Slides (short). Slides (long).
- Bin Packing via Discrepancy of Permutations. F. Eisenbrand, D. Palvoelgyi and T. Rothvoß. Invited submission to TALG SODA'11 special issue. Remark: This is the journal version of the SODA'11 paper. Since the conjecture of Beck has been disproved few months after SODA'11 by Newman and Nikolov, I recommend to read this journal version instead of the original SODA paper.
- A simpler proof for O(congestion + dilation) packet routing. T. Rothvoß. IPCO 2013. Slides.
- 0/1 Polytopes with Quadratic Chvátal Rank. T. Rothvoß and L. Sanità. IPCO 2013. Slides.
- Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. M. X. Goemans, N. Olver, T. Rothvoss, R. Zenklusen. STOC'12.
- The Entropy Rounding Method in Approximation Algorithms. T. Rothvoss. Symposium on Discrete Algorithms (SODA 2012), Kyoto, Japan, January 17-19, 2011. Slides (short). Slides (long).
- Extended formulations for polygons. S. Fiorini, T. Rothvoß, H. Raj Tiwary. Discrete & Computational Geometry. 2012.
- Some 0/1 polytopes need exponential size extended formulations. T. Rothvoss. Mathematical Programming. 2012. Slides.
- Cover-Decomposition and Polychromatic Numbers. B. Bollobás, D. Pritchard, T. Rothvoß, A. Scott. 19th Annual European Symposium on Algorithms (ESA 2011), Saarbrücken, Germany, 5.-9. September, 2011.
- A PTAS for the Highway Problem. F. Grandoni and T. Rothvoß. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011. Slides.
- Bin Packing via Discrepancy of Permutations. F. Eisenbrand, D. Palvoelgyi and T. Rothvoß. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011. Slides.
- From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk. F. Grandoni, T. Rothvoß and L. Sanità. Math. Oper. Res. 36(2): 185-204 (2011). Combined journal version of the APPROX'09 and ICALP'10 paper.
- Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. F. Eisenbrand, N. Kakimura, T. Rothvoß, L. Sanità. IPCO 2011.
- Approximation Algorithms for Single and Multi-Commodity Connected Facility Location. F. Grandoni and Thomas Rothvoß. IPCO 2011. Slides.
- Directed Steiner Tree and the Lasserre Hierarchy. T. Rothvoss. ArXiv ID 1111.5473. Slides.
- Diameter of Polyhedra: Limits of Abstraction. F. Eisenbrand, N. Hähnle, A. Razborov and T. Rothvoss. 2010. Journal version of the SOCG'09 paper.
- An Improved LP-based Approximation for Steiner Tree. J. Byrka, F. Grandoni, T. Rothvoß and L. Sanità. 42th ACM Symposium on Theory of Computing (STOC 2010, Best Paper Award), Cambridge, Massachusetts, USA, June 6-8, 2010. Slides.
- A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. A. Karrenbauer and T. Rothvoss. Approximation and Online Algorithms, 8th International Workshop (WAOA 2010), Liverpool, UK, September 9-10, 2010. Slides.
- Network Design via Core Detouring for Problems Without a Core. F. Grandoni and T. Rothvoss. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Slides.
- EDF-schedulability of synchronous periodic task systems is coNP-hard. F. Eisenbrand and T. Rothvoß. ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 17-19, 2010. Slides.
- Optimal selection of customers for a last-minute offer. R. Cominetti, J. R. Correa, T. Rothvoß and J. San Martín. Operations Research. 2010.
- Exact quantification of the sub-optimality of uni-processor fixed-priority preemptive scheduling. R. Davis, T. Rothvoß, S. Baruah and A. Burns. Real-time Systems. 2009.
- On the Complexity of the Asymmetric VPN Problem. T. Rothvoß and L. Sanità. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. Slides.
- New Hardness Results for Diophantine Approximation. F. Eisenbrand and T. Rothvoß. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. Slides.
- An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling. A. Karrenbauer and T. Rothvoß. 17th Annual European Symposium on Algorithms (ESA'09), Copenhagen, September 7-9, 2009. Slides.
- Diameter of Polyhedra: Limits of Abstraction. F. Eisenbrand, N. Hähnle and T. Rothvoß. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009
- Convexly independent subsets of the Minkowski sum of planar point sets. F. Eisenbrand, J. Pach, T. Rothvoß and N. B. Sopher. Electronic Journal of Combinatorics, Vol 15, 2008.
- Static-priority Real-time Scheduling: Response Time Computation is NP-hard. F. Eisenbrand and T. Rothvoß. Real-Time Systems Symposium (RTSS'08), Barcelona, Nov. 30-3 Dec., 2008.
- A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. F. Eisenbrand and T. Rothvoß. Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland, July 7-11, 2008. Slides.
- Approximating connected facility location problems via Random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß and G. Schäfer. Proceeding of Nineteenth annual ACM-SIAM Symposium (SODA '08), San Francisco, California, 20-22.01.2008. Slides.
- On the computational complexity of periodic scheduling. T. Rothvoss, (directed by F. Eisenbrand). PhD thesis. EPFL, Lausanne, Switzerland. 2009. Slides.
- Algorithms for Virtual Private Networks. T. Rothvoß (directed by F. Eisenbrand). Master's thesis. TU Dortmund, Germany. 2006.